#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;

class LRUCache{
public:
    LRUCache(int capa)
    :capacity(capa)
    {   
    }

    void put(int key, int value){
        // 通过key查找结点是否存在
        auto it = cache.find(key);
        if(it != cache.end()){  // 结点存在
            it->second->second = value; // 修改双向链表中对应结点的值
            dLinkedList.splice(dLinkedList.begin(), dLinkedList, it->second);   // 将该结点插入到双向链表的首部
        }else{  // 结点不存在
            if(cache.size() == capacity){   // cache已满
                auto deleteNode = dLinkedList.back();   // 获取最后一个结点元素
                // 删除最后一个结点
                dLinkedList.pop_back();
                cache.erase(deleteNode.first);
                // 插入新结点
                dLinkedList.push_front({key, value});
                cache[key] = dLinkedList.begin();
            }
            else{  // cache未满
                // 插入新结点
                dLinkedList.push_front({key, value});
                cache[key] = dLinkedList.begin();
            }
        }
    }

    int get(int key){
        auto it = cache.find(key);
        if(it != cache.end()){  // 结点存在
            // 置换结点
            dLinkedList.splice(dLinkedList.begin(), dLinkedList, it->second);
            return it->second->second;
        }else{
            return -1;
        }
    }

    void print(){
        for(auto &elem : dLinkedList){
            cout << "(" << elem.first << ","
                 << elem.second << ") ";
        }
        cout << endl;
    }

private:
    list<pair<int, int>> dLinkedList;   // 双向链表
    unordered_map<int, list<pair<int, int>>::iterator> cache;    // 哈希表
    int capacity;   // 容量
};

void test(){
    LRUCache lruCache(2);

    lruCache.put(1, 1);
    lruCache.print();
    
    lruCache.put(2, 2);
    lruCache.print();
    
    lruCache.get(1);
    lruCache.print();

    lruCache.put(3, 3);
    lruCache.print();

    lruCache.get(2);
    lruCache.print();

    lruCache.put(4, 4);
    lruCache.print();

    lruCache.get(1);
    lruCache.print();

    lruCache.get(3);
    lruCache.print();

    lruCache.get(4);
    lruCache.print();
}

int main(){
    test();
    return 0;
}